1. Field of the invention
The invention relates to the field of computer systems. More specifically, the invention relates to the antialiasing of video images.
2. Background information
In order to display three-dimensional objects, a computer system typically models the objects using polygons (e.g., triangles). When these polygons are drawn on a raster graphics display, the polygons are typically sampled at pixel centers. This technique causes non-vertical and non-horizontal polygon edges to appear jagged. When a polygon is moved slowly on a display, the "jags" on a jagged polygon edge appear to crawl as one views successive frames of the image (This visually annoying phenomenon is commonly known as the "crawling ants" or the "jaggies effect"). The jaggies effect is a well-known instance of a phenomenon known as aliasing. Operations that have the visual effect of removing the jaggies effect are referred to as "antialiasing" operations. For a further description of antialiasing, see Foley, James D., et al. Computer Graphics Principles and Practice, 2nd Edition, Addison-Wesley Publishing Co. (1990) pp. 132-144 (referred to herein as the "Foley" reference).
Improving the appearance of texture-mapped polygons requires antialiasing texture mapping, as well as antialiasing polygon edges. There are many well-known techniques for antialiasing texture mapping (see OpenGL Reference Manual: The Official Reference Document for OpenGL. Release 1, OpenGL Architecture Review Board, Addison-Wesley Publishing Co. (1992) pp. 295-296). One such technique employs bilinear filtering. When applying bilinear filtering, the output pixel is a function of four adjacent input pixels and can be considered a 2.times.2 convolution with weights as shown below: ##EQU1## where f.sub.1, and f.sub.2 are in the range [0,1].
The techniques of antialiasing polygon edges fall into one of three categories: pre-processing, multi-sampling, and post-processing. The pre-processing techniques require the antialiasing operations to be performed before a scene is "rendered" (The term "rendered" is used herein to refer to the conversion of a set of polygons into a set of pixel data representative of an image to be displayed on a computer screen). Typically, the pre-processing techniques are computation intensive and require additional hardware (e.g., an "alpha" buffer). For a description of pre-processing techniques, see OpenGL Reference Manual: The Official Reference Document for OpenGL, Release 1, OpenGL Architecture Review Board, Addison-Wesley Publishing Co. (1992) pp. 295-296; and Niimi, Haruo et al. A Parallel Processor System for Three-Dimensional Color Graphics, Computer Graphics, Vol. 18, No. 3 (July 1984), pp. 67-76. The multi-sampling techniques require rendering the entire scene multiple times (or at a higher resolution) and accumulating the results. As a result, the multi-sampling techniques typically require expensive hardware to maintain a high frame rate when drawing each pixel many times (typically 8-16 times). In addition, the multi-sampling techniques are currently too slow for low-cost, real time three-dimensional graphics rendering. For a further description of multi-sampling techniques, see Akeley, Kurt. Reality Engine Graphics, Computer Graphics Proceedings, Association for Computing Machinery, Inc. (1993), pp. 109-126.
The post-processing technique is taught in Bloomenthal, Jules. Edge Inference with Applications to Antialiasing, Computer Graphics, Vol. 17, No. 3 (July 1983), pp. 157-162 (referred to herein as the "Bloomenthal" reference). The Bloomenthal reference describes the following steps: 1) rendering an entire non-texture mapped scene with aliased polygon edges; 2) inferring the polygon edges in the scene; and 3) antialiasing polygon edges in the non-texture mapped scene by modifying certain output pixels based on values of certain input pixels in the scene. The manner in which the output pixels are modified is determined using a digital box filter. The digital box filter requires computing the intersection of the pixel with the polygon, computing the area of this intersection, and computing the convolution weights from this area. Unfortunately, due to the computational effort required to infer the polygon edges and to determine the exact areas of intersection, this technique is currently too slow to be commercially viable.